{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Bags With Full Capacity of Rocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #装满石头的背包的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有编号从&nbsp;<code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个背包。给你两个下标从 <strong>0</strong> 开始的整数数组 <code>capacity</code> 和 <code>rocks</code> 。第 <code>i</code> 个背包最大可以装 <code>capacity[i]</code> 块石头，当前已经装了 <code>rocks[i]</code> 块石头。另给你一个整数 <code>additionalRocks</code> ，表示<span class=\"text-only\" data-eleid=\"10\" style=\"white-space: pre;\">你可以放置的额外石头数量，石头可以往 </span><strong><span class=\"text-only\" data-eleid=\"11\" style=\"white-space: pre;\">任意</span></strong><span class=\"text-only\" data-eleid=\"12\" style=\"white-space: pre;\"> 背包中放置。</span></p>\n",
    "\n",
    "<p>请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 <strong>最大 </strong>数量<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "1 块石头放入背包 0 ，1 块石头放入背包 1 。\n",
    "每个背包中的石头总数是 [2,3,4,4] 。\n",
    "背包 0 、背包 1 和 背包 2 都装满石头。\n",
    "总计 3 个背包装满石头，所以返回 3 。\n",
    "可以证明不存在超过 3 个背包装满石头的情况。\n",
    "注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "8 块石头放入背包 0 ，2 块石头放入背包 2 。\n",
    "每个背包中的石头总数是 [10,2,2] 。\n",
    "背包 0 、背包 1 和背包 2 都装满石头。\n",
    "总计 3 个背包装满石头，所以返回 3 。\n",
    "可以证明不存在超过 3 个背包装满石头的情况。\n",
    "注意，不必用完所有的额外石头。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == capacity.length == rocks.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= capacity[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= rocks[i] &lt;= capacity[i]</code></li>\n",
    "\t<li><code>1 &lt;= additionalRocks &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-bags-with-full-capacity-of-rocks](https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-bags-with-full-capacity-of-rocks](https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,4,5]\\n[1,2,4,4]\\n2', '[10,2,2]\\n[2,2,0]\\n100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            capacity[i] -= rocks[i]\n",
    "        capacity.sort()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if capacity[i] == 0:\n",
    "                res += 1\n",
    "            else:\n",
    "                t = min(capacity[i], additionalRocks)\n",
    "                capacity[i] -= t\n",
    "                additionalRocks -= t\n",
    "                if capacity[i] == 0:\n",
    "                    res += 1\n",
    "                if additionalRocks == 0:\n",
    "                    break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        if sum(capacity)<=sum(rocks)+additionalRocks:\n",
    "            return n\n",
    "        for i in range(n):\n",
    "            capacity[i]-=rocks[i]\n",
    "        capacity.sort()\n",
    "        i=0\n",
    "        while i<n and additionalRocks>=capacity[i]  :\n",
    "            additionalRocks-=capacity[i]\n",
    "            i+=1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: list[int], rocks: list[int], additionalRocks: int) -> int:\n",
    "        # sub = []\n",
    "        mea = len(capacity)\n",
    "        for i in range(mea):\n",
    "            rocks[i] = capacity[i] - rocks[i]\n",
    "        i = 0\n",
    "        rocks.sort()\n",
    "        while i < mea and additionalRocks > 0:\n",
    "            if rocks[i] > additionalRocks:\n",
    "                break\n",
    "            additionalRocks -= rocks[i]\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            capacity[i] -= rocks[i]\n",
    "        count = 0\n",
    "        for x in sorted(capacity):\n",
    "            if additionalRocks < x:\n",
    "                break\n",
    "            additionalRocks -= x\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        for i in range(len(capacity)):\n",
    "            capacity[i] -= rocks[i]\n",
    "        capacity.sort()\n",
    "        \n",
    "        ret = 0\n",
    "        i = 0\n",
    "        while i < len(capacity) and additionalRocks > 0:\n",
    "            additionalRocks -= capacity[i]\n",
    "            ret += 1 if additionalRocks >= 0 else 0\n",
    "            i+= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        for i in range(len(capacity)):\n",
    "            capacity[i] -= rocks[i]\n",
    "        capacity.sort()\n",
    "        num = 0\n",
    "        for i in range(len(capacity)):\n",
    "            if additionalRocks>=capacity[i]:\n",
    "                additionalRocks-=capacity[i]\n",
    "                num += 1\n",
    "            else:\n",
    "                break\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        for i in range(len(capacity)):\n",
    "            capacity[i] -= rocks[i]\n",
    "\n",
    "        capacity.sort()\n",
    "        ans = 0\n",
    "        for cap in capacity:\n",
    "            if cap >= 0 and additionalRocks - cap >= 0:\n",
    "                additionalRocks -= cap\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    print(s.maximumBags([2, 3, 4, 5], [1, 2, 4, 4], 2))\n",
    "    print(s.maximumBags([10, 2, 2], [2, 2, 0], 100))\n",
    "    print(s.maximumBags([8, 2, 2], [1, 2, 0], 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        for i in range(len(capacity)):\n",
    "            capacity[i] -= rocks[i]\n",
    "        capacity.sort()\n",
    "        num = 0\n",
    "        i=0\n",
    "        while additionalRocks > 0 and i<len(capacity):\n",
    "            if additionalRocks>=capacity[i]:\n",
    "                additionalRocks-=capacity[i]\n",
    "                num += 1\n",
    "            else:\n",
    "                break\n",
    "            i+=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        if sum(capacity) <= additionalRocks + sum(rocks):\n",
    "            return len(capacity)\n",
    "        \n",
    "        add = []\n",
    "        for i in range(len(capacity)):\n",
    "            add.append(capacity[i]-rocks[i])\n",
    "        \n",
    "        add.sort()\n",
    "\n",
    "        i=0\n",
    "        res = 0\n",
    "        while additionalRocks > 0 and i < len(capacity):\n",
    "            if add[i] <= additionalRocks:\n",
    "                additionalRocks -= add[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "           \n",
    "        \n",
    "        return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        for i in range(len(capacity)):\n",
    "            capacity[i] = capacity[i] - rocks[i]\n",
    "        capacity.sort()\n",
    "        count = capacity.count(0)\n",
    "        for i in range(count, len(capacity)):\n",
    "            if additionalRocks >= capacity[i]:\n",
    "                additionalRocks -= capacity[i]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return count\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        diff = []\n",
    "        for i in range(len(rocks)):\n",
    "            diff.append(capacity[i]-rocks[i])\n",
    "        diff.sort()\n",
    "        j = 0\n",
    "        res = 0\n",
    "        while additionalRocks >= 0 and j < len(rocks):\n",
    "            additionalRocks -= diff[j]\n",
    "            if additionalRocks >= 0:\n",
    "                res += 1\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "\n",
    "        to_fill = []\n",
    "        for i1, i2 in zip(capacity, rocks):\n",
    "            to_fill.append(i1-i2)\n",
    "\n",
    "        sort_to_fill = sorted(to_fill)\n",
    "\n",
    "        res_num = 0\n",
    "        for i in range(len(sort_to_fill)):\n",
    "\n",
    "            if sort_to_fill[i] == 0:\n",
    "                res_num += 1\n",
    "            elif sort_to_fill[i] <= additionalRocks:\n",
    "                res_num += 1\n",
    "                additionalRocks -= sort_to_fill[i]\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return res_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "    #     temp_list = []\n",
    "    #     for i in range(len(capacity)):\n",
    "    #         temp_list.append(capacity[i]-rocks[i])\n",
    "    #     temp_list.sort()\n",
    "        # for x in range(len(temp_list)):\n",
    "        #     if temp_list[x] <= additionalRocks:\n",
    "        #         additionalRocks -= temp_list[x]\n",
    "        #         temp_list[x] = 0\n",
    "        #     else:\n",
    "        #         break\n",
    "        # return temp_list.count(0)\n",
    "        def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "            if sum(capacity) <= additionalRocks + sum(rocks):\n",
    "                return len(capacity)\n",
    "            arr = []\n",
    "            for i in range(len(capacity)):\n",
    "                arr.append(capacity[i] - rocks[i])\n",
    "            arr.sort()\n",
    "            i = 0\n",
    "            res = 0\n",
    "            while additionalRocks > 0 and i < len(capacity):\n",
    "                if arr[i] <= additionalRocks:\n",
    "                    additionalRocks -= arr[i]\n",
    "                    res += 1\n",
    "                i += 1\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        res=[capacity[i]-rocks[i] for i in range(len(capacity))]\n",
    "        res.sort()\n",
    "        c=0\n",
    "        for i in range(len(rocks)):\n",
    "            if(additionalRocks>=res[i]):\n",
    "                additionalRocks-=res[i]\n",
    "                c+=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        if sum(capacity) <= additionalRocks + sum(rocks):\n",
    "            return len(capacity)\n",
    "        arr = []\n",
    "        for i in range(len(capacity)):\n",
    "            arr.append(capacity[i] - rocks[i])\n",
    "            arr.sort()\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while additionalRocks > 0 and i < len(capacity):\n",
    "            if arr[i] <= additionalRocks:\n",
    "                additionalRocks -= arr[i]\n",
    "                res +=1\n",
    "            i += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        a = list(capacity[i]-rocks[i] for i in range(len(capacity)))\n",
    "        a.sort()\n",
    "        c = 0\n",
    "        for idx,val in enumerate(a):\n",
    "            c+=val\n",
    "            if c>additionalRocks:\n",
    "                return idx\n",
    "        return len(a)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        if sum(capacity) <= sum(rocks) + additionalRocks:\n",
    "            return len(capacity)\n",
    "        \n",
    "        lst = [x - y  for x, y in zip(capacity, rocks)]\n",
    "        lst.sort()\n",
    "        i = 0\n",
    "        while additionalRocks >= lst[i]:\n",
    "            additionalRocks-= lst[i]\n",
    "            i+= 1\n",
    "        return i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        arr = [0] * n\n",
    "        # 获取每个背包差多少能装满\n",
    "        for i in range(n):\n",
    "            arr[i] = capacity[i] - rocks[i]\n",
    "        # 从小到大排序\n",
    "        arr.sort()\n",
    "        print('arr', arr)\n",
    "        res = 0     # 统计装满前i个背包所需的石头\n",
    "        for i in range(n):\n",
    "            res += arr[i]\n",
    "            # 刚好能装满，则返回i+1（下标从零开始）\n",
    "            if res == additionalRocks:\n",
    "                return i + 1\n",
    "            # 如果装上第i个时 比additionalRocks大，说明additionalRocks不足以装满国有背包，返回i\n",
    "            if res > additionalRocks:\n",
    "                return i \n",
    "        # additionalRocks数量足够多，所有背包都能装满，返回背包数\n",
    "        return n\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        i = 0\n",
    "        remain_room = []\n",
    "        while i < len(capacity):\n",
    "            remain_room.append(capacity[i]-rocks[i])\n",
    "            i += 1\n",
    "        remain_room = sorted(remain_room)\n",
    "        j = 0\n",
    "        count = 0\n",
    "        while j < len(remain_room):\n",
    "            if additionalRocks >= remain_room[j]:\n",
    "                additionalRocks -= remain_room[j]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "            j += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        rest = []\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            rest.append(capacity[i] - rocks[i])\n",
    "        rest.sort()\n",
    "        cnt = 0\n",
    "        stone = additionalRocks\n",
    "        print(rest)\n",
    "        for r in rest:\n",
    "            if stone <= 0:\n",
    "                break\n",
    "            if r == 0:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            if stone - r >= 0:\n",
    "                cnt += 1\n",
    "                stone = stone - r\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        length = len(capacity)\n",
    "        diffOf = [0] * length\n",
    "\n",
    "        for i in range(length):\n",
    "            diffOf[i] = capacity[i] - rocks[i]\n",
    "\n",
    "        diffOf = sorted(diffOf, key=lambda x:x)\n",
    "        print(str(diffOf))\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(length):\n",
    "            if diffOf[i] == 0:\n",
    "                ans += 1\n",
    "                print(\"1111\")\n",
    "                continue\n",
    "\n",
    "            if (additionalRocks - diffOf[i] >= 0):\n",
    "                additionalRocks -= diffOf[i]\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        rest = [i-j for i, j in zip(capacity, rocks)]\n",
    "        rest.sort(reverse=False)\n",
    "        print(rest)\n",
    "        p = 0\n",
    "        while p < len(rest) and additionalRocks > 0:\n",
    "            if rest[p] == 0:\n",
    "                p += 1\n",
    "            elif rest[p] <= additionalRocks:\n",
    "                additionalRocks -= rest[p]\n",
    "                rest[p] = 0\n",
    "                p += 1\n",
    "            else:\n",
    "                break\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        length = len(capacity)\n",
    "        new_nums = [0]*length\n",
    "        for i in range(length):\n",
    "            new_nums[i] = capacity[i]-rocks[i]\n",
    "        new_nums.sort()\n",
    "        for i in range(length):\n",
    "            if new_nums[i]<=additionalRocks:\n",
    "                additionalRocks = additionalRocks - new_nums[i]\n",
    "                new_nums[i]=0\n",
    "            else:\n",
    "                break\n",
    "        return new_nums.count(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        ans = [0] * n\n",
    "        for i, (x, y) in enumerate(zip(capacity, rocks)):\n",
    "            ans[i] = x - y\n",
    "        ans.sort()\n",
    "        c = 0\n",
    "        t = 0\n",
    "        for x in ans:\n",
    "            c += x\n",
    "            if c > additionalRocks:\n",
    "                break\n",
    "            t += 1\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        # 初始化二维数组dp\n",
    "        #n = len(capacity)\n",
    "        #dp = [[0] * (additionalRocks + 1) for _ in range(n + 1)]\n",
    "        # 遍历每个背包和每个石头数量\n",
    "        #for i in range(1, n + 1):\n",
    "        #    for j in range(additionalRocks + 1):\n",
    "        #        # 不使用第i个背包\n",
    "        #        dp[i][j] = dp[i - 1][j]\n",
    "                # 使用第i个背包\n",
    "        #        if capacity[i - 1] - rocks[i - 1] <= j:\n",
    "                    # 第i个背包可以装满\n",
    "        #            dp[i][j] = max(dp[i][j], dp[i - 1][j - (capacity[i - 1] - rocks[i - 1])] + 1)\n",
    "        # 返回最终结果\n",
    "        #return dp[n][additionalRocks]\n",
    "\n",
    "        n = len(capacity)\n",
    "        rest = [0] * n\n",
    "        for i in range(n):\n",
    "            rest[i] = capacity[i] - rocks[i]\n",
    "        rest.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while additionalRocks > 0 and i < n:\n",
    "            if rest[i] <= additionalRocks:\n",
    "                additionalRocks -= rest[i]\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: list[int], rocks: list[int], additionalRocks: int) -> int:\n",
    "        sub = []\n",
    "        mea = len(capacity)\n",
    "        for i in range(mea):\n",
    "            if capacity[i] - rocks[i] > 0:\n",
    "                sub.append(capacity[i] - rocks[i])\n",
    "        i = 0\n",
    "        sub.sort()\n",
    "        mea1 = len(sub)\n",
    "        while i < mea1 and additionalRocks > 0:\n",
    "            if sub[i] > additionalRocks:\n",
    "                break\n",
    "            additionalRocks -= sub[i]\n",
    "            i += 1\n",
    "        return i+(mea - mea1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        s = [a - b for a, b in zip(capacity, rocks)]\n",
    "        s.sort()\n",
    "        ans = 0\n",
    "        m = additionalRocks\n",
    "        for x in s:\n",
    "            if m >= x:\n",
    "                m -= x\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        count_bag = len(capacity) \n",
    "        shortage = [0] * count_bag\n",
    "        for ind in range(count_bag):\n",
    "            shortage[ind] = capacity[ind] - rocks[ind]\n",
    "\n",
    "        shortage.sort()\n",
    "        i = 0 \n",
    "        while i < count_bag and additionalRocks >= shortage[i]:\n",
    "            additionalRocks -= shortage[i]\n",
    "            i += 1\n",
    "\n",
    "        return i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        rest = [0] * n\n",
    "        for i in range(n):\n",
    "            rest[i] = capacity[i] - rocks[i]\n",
    "        rest.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while additionalRocks > 0 and i < n:\n",
    "            if rest[i] <= additionalRocks:\n",
    "                additionalRocks -= rest[i]\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        rest = [0] * n\n",
    "        for i in range(n):\n",
    "            rest[i] = capacity[i] - rocks[i]\n",
    "        rest.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while additionalRocks > 0 and i < n:\n",
    "            if rest[i] <= additionalRocks:\n",
    "                additionalRocks -= rest[i]\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        rs=[]\n",
    "        for i in range(len(capacity)):\n",
    "            rs.append(capacity[i]-rocks[i])\n",
    "        rs.sort()\n",
    "\n",
    "        for i in range(len(rs)):\n",
    "\n",
    "            if rs[i]<=additionalRocks:\n",
    "                additionalRocks-=rs[i]\n",
    "                rs[i]=0\n",
    "                \n",
    "        pt=0\n",
    "\n",
    "        for i in rs:\n",
    "            if i==0:\n",
    "                pt+=1\n",
    "        return pt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        lst=[]\n",
    "        n=len(capacity)\n",
    "        for i in range(n):\n",
    "            lst.append(capacity[i]-rocks[i])\n",
    "        lst.sort()\n",
    "        j=0\n",
    "        ans=0\n",
    "        while additionalRocks>0 and j<=n-1:\n",
    "            if lst[j]==0:\n",
    "                ans+=1\n",
    "            elif additionalRocks>=lst[j]:\n",
    "                additionalRocks-=lst[j]\n",
    "                ans+=1\n",
    "            else:\n",
    "                additionalRocks=0\n",
    "            j+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr=[]\n",
    "        for a,b in zip(capacity,rocks):\n",
    "            arr.append(a-b)\n",
    "        arr.sort()\n",
    "        p=0\n",
    "        ans=0\n",
    "        while p<len(arr) and additionalRocks-arr[p]>=0:\n",
    "            additionalRocks-=arr[p]\n",
    "            ans+=1\n",
    "            p+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: list[int], rocks: list[int], additionalRocks: int) -> int:\n",
    "        less_rock = list(map(lambda x,y:x-y, capacity, rocks))\n",
    "        less_rock.sort()\n",
    "        ans = 0\n",
    "        rocks_sum = 0\n",
    "        for item in less_rock:\n",
    "            rocks_sum += item\n",
    "            if rocks_sum <= additionalRocks:\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        diff = [ (capacity[i] - rocks[i]) for i in range(n) ]\n",
    "        diff = sorted(diff)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            additionalRocks -= diff[i]\n",
    "            if additionalRocks >= 0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        need = []\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            heapq.heappush(need, capacity[i]-rocks[i])\n",
    "        ans = 0\n",
    "        while need and additionalRocks > 0:\n",
    "            mid = heapq.heappop(need)\n",
    "            if additionalRocks >= mid:\n",
    "                ans += 1\n",
    "            additionalRocks -= mid\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], a: int) -> int:\n",
    "        q=[x-y for x,y in zip(capacity,rocks)]\n",
    "        q.sort()\n",
    "        print(q)\n",
    "        i=0\n",
    "        while i<len(capacity) and a-q[i]>=0:\n",
    "            a-=q[i]\n",
    "            i+=1\n",
    "        return i    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        rest = []\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            rest.append(capacity[i] - rocks[i])\n",
    "        rest.sort()\n",
    "        additionalRocks_rest = additionalRocks\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if additionalRocks_rest >= rest[i]:\n",
    "                additionalRocks_rest = additionalRocks_rest - rest[i]\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        m=len(capacity)\n",
    "        diff=sorted([c-r for c,r in zip(capacity,rocks) if c-r!=0])\n",
    "        n=len(diff)\n",
    "        s=0\n",
    "        for i in range(n):\n",
    "            s+=diff[i]\n",
    "            if s>additionalRocks:\n",
    "                return m-n+i\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    full_count = float(\"-inf\")\n",
    "\n",
    "    def maximumBags(\n",
    "        self, capacity: List[int], rocks: List[int], additionalRocks: int\n",
    "    ) -> int:\n",
    "        bag_count = len(capacity)\n",
    "        res_rocks = sorted([capacity[i] - rocks[i] for i in range(bag_count)])\n",
    "\n",
    "        idx = 0\n",
    "        while idx < bag_count and additionalRocks >= res_rocks[idx]:\n",
    "            additionalRocks -= res_rocks[idx]\n",
    "            idx += 1\n",
    "\n",
    "        return idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        need = []\n",
    "        for c,r in zip(capacity,rocks):\n",
    "            need.append(c-r)\n",
    "\n",
    "        need.sort()\n",
    "        print(need)\n",
    "        count = 0\n",
    "        index = 0 # 表示有背包可以放石头\n",
    "        while additionalRocks >= 0 and index < len(capacity):\n",
    "            if need[index] <= additionalRocks:\n",
    "                additionalRocks -= need[index]\n",
    "            else:\n",
    "                break\n",
    "            index += 1\n",
    "            count += 1\n",
    "        return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        capacity = sorted([capacity[i]-rocks[i] for i in range(n)])\n",
    "        ans = 0\n",
    "        for i in capacity:\n",
    "            if i > additionalRocks:\n",
    "                break\n",
    "            ans += 1\n",
    "            additionalRocks -= i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        need = []\n",
    "        n = len(capacity)\n",
    "        for i in range(n):\n",
    "            heapq.heappush(need, capacity[i]-rocks[i])\n",
    "        ans = 0\n",
    "        while need and additionalRocks > 0:\n",
    "            mid = heapq.heappop(need)\n",
    "            if additionalRocks >= mid:\n",
    "                ans += 1\n",
    "            additionalRocks -= mid\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        remain = []\n",
    "        full = 0\n",
    "        for i in range(len(capacity)):\n",
    "            remain_space = capacity[i] - rocks[i]\n",
    "            if remain_space == 0:\n",
    "                full += 1\n",
    "            else:\n",
    "                remain.append(remain_space)\n",
    "        remain.sort()\n",
    "        print(remain)\n",
    "\n",
    "        for space in remain:\n",
    "            if additionalRocks == 0:\n",
    "                return full\n",
    "            if space <= additionalRocks:\n",
    "                additionalRocks -= space\n",
    "                full += 1\n",
    "            else:\n",
    "                additionalRocks = 0\n",
    "        return full"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        remain = []\n",
    "        full = 0\n",
    "        for i in range(len(capacity)):\n",
    "            remain_space = capacity[i] - rocks[i]\n",
    "            if remain_space == 0:\n",
    "                full += 1\n",
    "            else:\n",
    "                remain.append(remain_space)\n",
    "        remain.sort()\n",
    "        print(remain)\n",
    "\n",
    "        for space in remain:\n",
    "            if additionalRocks == 0:\n",
    "                return full\n",
    "            if space <= additionalRocks:\n",
    "                additionalRocks -= space\n",
    "                full += 1\n",
    "            else:\n",
    "                additionalRocks = 0\n",
    "        return full"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        left = []\n",
    "        for i in range(len(capacity)):\n",
    "            left.append(capacity[i] - rocks[i])\n",
    "        left.sort()\n",
    "        print(left)\n",
    "        cnt = 0\n",
    "        for i in range(len(left)):\n",
    "            if left[i] == 0:\n",
    "                cnt += 1\n",
    "            elif left[i] <= additionalRocks:\n",
    "                cnt += 1\n",
    "                additionalRocks -= left[i]\n",
    "                if additionalRocks == 0:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        # Calculate the rocks needed to fill each bag\n",
    "        rocks_needed = [capacity[i] - rocks[i] for i in range(len(capacity))]\n",
    "        \n",
    "        # Use a min-heap to get the bag that requires the least rocks to fill\n",
    "        heapq.heapify(rocks_needed)\n",
    "        \n",
    "        filled_bags = 0\n",
    "        \n",
    "        # While we have additional rocks and the heap is not empty\n",
    "        while additionalRocks > 0 and rocks_needed:\n",
    "            # Get the bag that requires the least rocks to fill\n",
    "            needed = heapq.heappop(rocks_needed)\n",
    "            \n",
    "            # If the bag can be filled with the available rocks\n",
    "            if additionalRocks >= needed:\n",
    "                filled_bags += 1\n",
    "                additionalRocks -= needed\n",
    "        \n",
    "        return filled_bags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        # 贪心算法\n",
    "        # 计算哪个背包剩余容量最少，先把石头填充到该背包里面\n",
    "        # 先对背包容量和背包中已经装的石头做差\n",
    "        # 堆排序\n",
    "        class heap:\n",
    "            def __init__(self):\n",
    "                self.diffs=[]\n",
    "            \n",
    "            def swap(self,i,j):\n",
    "                tmp=self.diffs[i]\n",
    "                self.diffs[i]=self.diffs[j]\n",
    "                self.diffs[j]=tmp\n",
    "            # 向diffs中加入一个元素，将该元素调整到合适的位置\n",
    "            def heapify(self,num):\n",
    "                self.diffs.append(num)\n",
    "                i=len(self.diffs)-1\n",
    "                while i>0:\n",
    "                    parent=(i-1)//2\n",
    "                    if self.diffs[parent]>self.diffs[i]:\n",
    "                        self.swap(parent,i)\n",
    "                        i=parent\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            def pop(self):\n",
    "                # 每次弹出一个堆顶元素，都要重新调整堆结构\n",
    "                self.swap(0,len(self.diffs)-1)\n",
    "                last_num=self.diffs.pop()\n",
    "                last_idx=len(self.diffs)\n",
    "                i=0\n",
    "                while i<last_idx:\n",
    "                    # 先求出左右子树根节点的最小值\n",
    "                    idx=2*i+1\n",
    "                    max_idx=idx\n",
    "                    if idx>=last_idx:\n",
    "                        break\n",
    "                    if idx+1>=last_idx:\n",
    "                        pass\n",
    "                    else:\n",
    "                        if self.diffs[idx]>self.diffs[idx+1]:\n",
    "                            max_idx=idx+1\n",
    "                    if self.diffs[i]>self.diffs[max_idx]:\n",
    "                        self.swap(i,max_idx)\n",
    "                        i=max_idx\n",
    "                    else:\n",
    "                        break\n",
    "                return last_num\n",
    "\n",
    "        hp=heap()\n",
    "\n",
    "        for i in range(len(capacity)):\n",
    "            hp.heapify(capacity[i]-rocks[i])\n",
    "        \n",
    "        count=0\n",
    "        while additionalRocks>0 and hp.diffs:\n",
    "            num=hp.pop()\n",
    "            if num<=additionalRocks:\n",
    "                count+=1\n",
    "                additionalRocks-=num\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        gap = []\n",
    "        for i in range(len(capacity)):\n",
    "            gap.append(capacity[i] - rocks[i])\n",
    "        gap.sort()\n",
    "        i = 0\n",
    "        while additionalRocks > 0 and i < len(gap):\n",
    "            if gap[i] == 0:\n",
    "                i+=1\n",
    "                continue\n",
    "            if additionalRocks - gap[i] >= 0:\n",
    "                additionalRocks -= gap[i]\n",
    "                gap[i] = 0\n",
    "            else:\n",
    "                additionalRocks -= gap[i]\n",
    "                gap[i] -= additionalRocks\n",
    "            i+=1\n",
    "        return Counter(gap)[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        gap = Counter([ii - jj for ii, jj in zip(capacity, rocks)])\n",
    "        res = gap.get(0, 0)\n",
    "        pre = additionalRocks\n",
    "        for ii in sorted(gap.keys()):\n",
    "            if ii == 0:\n",
    "                continue\n",
    "            tmp = min(pre // ii, gap[ii])\n",
    "            res += tmp\n",
    "            pre -= tmp * ii\n",
    "            if pre < ii:\n",
    "                break\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        capacity=[capacity[i]-rocks[i] for i in range(len(rocks))]\n",
    "\n",
    "        capacity=sorted(capacity)\n",
    "\n",
    "        print(capacity)\n",
    "        i,n=0,len(rocks)\n",
    "        count=0\n",
    "\n",
    "        while(i<n and additionalRocks>=0):\n",
    "            if capacity[i]!=0 and capacity[i]<=additionalRocks:\n",
    "                additionalRocks=additionalRocks-capacity[i]\n",
    "                capacity[i]=0\n",
    "                # print()\n",
    "            \n",
    "            if capacity[i]==0:\n",
    "                count+=1\n",
    "            # print(capacity[i],additionalRocks)\n",
    "            i=i+1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        ans = 0\n",
    "        rems = [a-b for a,b in zip(capacity,rocks)]\n",
    "        rems = sorted(rems)\n",
    "        print(rems)\n",
    "        sum = 0\n",
    "        for rem in rems:\n",
    "            sum+=rem\n",
    "            if sum<=additionalRocks:\n",
    "                ans+=1\n",
    "            else: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        left_list = [(capacity[i] - rocks[i]) for i in range(len(rocks))]\n",
    "        left_list.sort(reverse = False)\n",
    "        flag = 1\n",
    "        j = 0\n",
    "        dp = 0\n",
    "        print(left_list)\n",
    "        for i in range(len(left_list)):\n",
    "            if (dp+left_list[i]) <= additionalRocks:\n",
    "                dp += left_list[i]\n",
    "                j += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr = list(accumulate(sorted(x - y for x, y in zip(capacity, rocks))))\n",
    "        return bisect_right(arr, additionalRocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr = list(accumulate(sorted(x - y for x, y in zip(capacity, rocks))))\n",
    "        return bisect_right(arr, additionalRocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        rest = [cap - cur for cap, cur in zip(capacity, rocks)]\n",
    "        if additionalRocks >= sum(rest):\n",
    "            return len(rest)\n",
    "        rest_idx = sorted([i for i in range(len(rest))], key=lambda x:rest[x])\n",
    "        ans = rest.count(0)\n",
    "        for idx in rest_idx:\n",
    "            if rest[idx] == 0:\n",
    "                continue\n",
    "            if additionalRocks>= rest[idx]:\n",
    "                additionalRocks -= rest[idx]\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        needs=[]\n",
    "        n=len(capacity)\n",
    "        for i in range(n):\n",
    "            needs.append(capacity[i]-rocks[i])\n",
    "        needs=sorted(needs)\n",
    "        print(needs)\n",
    "        j=0\n",
    "        while additionalRocks>0 and j<n:\n",
    "            if needs[j]<=additionalRocks:\n",
    "                \n",
    "                additionalRocks-=needs[j]\n",
    "                needs[j]=0\n",
    "            j+=1\n",
    "        cnt=collections.Counter(needs)\n",
    "        \n",
    "        return cnt.get(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        res = 0\n",
    "        l = list(zip(capacity, rocks))\n",
    "        l.sort(key=lambda x: x[0] - x[1])\n",
    "        for i, j in l:\n",
    "            if i > j:\n",
    "                t = i - j\n",
    "                if additionalRocks >= t:\n",
    "                    additionalRocks -= t\n",
    "                    res += 1\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        if sum(rocks)+additionalRocks>=sum(capacity):\n",
    "            return len(capacity)\n",
    "        \n",
    "        cr=[[capacity[i],rocks[i]] for i in range(0,len(capacity))]\n",
    "        cr.sort(key=lambda x:x[0]-x[1])\n",
    "        shengyu=additionalRocks\n",
    "        a=0\n",
    "        n=0\n",
    "        for cap,roc in cr:\n",
    "            if roc==cap :\n",
    "                a+=1\n",
    "                continue\n",
    "            if shengyu>=cap-roc:\n",
    "                shengyu-=(cap-roc)\n",
    "                a+=1\n",
    "                    \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], left: int) -> int:\n",
    "        lis = list(zip(rocks, capacity))\n",
    "        lis.sort(key = lambda x: -x[0] + x[1])\n",
    "        i = 0 \n",
    "        res = 0\n",
    "        while i < len(lis) and left:\n",
    "            # print(lis[i])\n",
    "            need = lis[i][1] - lis[i][0]\n",
    "            if left >= need:\n",
    "                left -= need\n",
    "                i += 1\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        lst = []\n",
    "        n = len(rocks)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            lst.append([rocks[i], capacity[i]])\n",
    "        \n",
    "        lst.sort(key = lambda x: x[1]-x[0])\n",
    "\n",
    "        for i in range(n):\n",
    "            diff = lst[i][1]-lst[i][0]\n",
    "            if additionalRocks >= diff:\n",
    "                res += 1\n",
    "                additionalRocks -= diff\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        \n",
    "        from collections import Counter\n",
    "        remain = additionalRocks\n",
    "        full = 0\n",
    "        l = len(rocks)\n",
    "        \n",
    "        diffs = []\n",
    "        for i in range(l):\n",
    "            diffs.append(capacity[i] - rocks[i])\n",
    "        diffs.sort()\n",
    "        for i, diff in enumerate(diffs):\n",
    "            remain -= diff\n",
    "            if remain < 0: break\n",
    "            diffs[i] = 0\n",
    "        \n",
    "        counter = Counter(diffs)\n",
    "        print(counter)\n",
    "        # print(counter[0])\n",
    "        \n",
    "        return counter[0]\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        data = []\n",
    "        for i in range(n):\n",
    "            data.append((capacity[i], rocks[i]))\n",
    "        data.sort(key=lambda x: x[0]-x[1])\n",
    "        res, yu = 0, additionalRocks\n",
    "        for x, y in data:\n",
    "            if x - y <= yu:\n",
    "                res += 1\n",
    "                yu -= x - y\n",
    "            else:\n",
    "                break\n",
    "            if yu == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "\n",
    "        n = len(capacity)\n",
    "        res = 0\n",
    "        for diff in sorted(zip(capacity, rocks), key = lambda x:x[0] - x[1]):\n",
    "            additionalRocks -= (diff[0] - diff[1])\n",
    "            if additionalRocks >= 0:\n",
    "                res += 1\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        for diff in sorted(zip(capacity, rocks), key = lambda x:x[0] - x[1]):\n",
    "            additionalRocks -= (diff[0] - diff[1])\n",
    "            if additionalRocks >= 0:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        a = additionalRocks\n",
    "        d = list(zip(capacity,rocks))\n",
    "        # print(d)\n",
    "        lst = sorted(d, key = lambda x:x[0]-x[1])\n",
    "        # print(lst)\n",
    "        res = 0\n",
    "        for x, y in lst:\n",
    "            if x != y:\n",
    "                tmp = x - y\n",
    "                if a == 0:\n",
    "                    return res\n",
    "                elif tmp > a:\n",
    "                    return res \n",
    "                else:\n",
    "                    res += 1\n",
    "                    a -= tmp\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        ans = 0\n",
    "        for a, b in sorted(zip(capacity, rocks),key=lambda x:x[0]-x[1]):\n",
    "            v = a - b\n",
    "            if v > additionalRocks:\n",
    "                break\n",
    "            else:\n",
    "                additionalRocks -= v\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        n = len(capacity)\n",
    "        indicies = sorted(list(range(n)), key = lambda i: capacity[i] - rocks[i])\n",
    "        res = 0\n",
    "        \n",
    "        for i in indicies:\n",
    "            diff = capacity[i] - rocks[i]\n",
    "            if diff == 0:\n",
    "                res += 1\n",
    "            elif additionalRocks >= diff:\n",
    "                additionalRocks -= diff\n",
    "                res += 1\n",
    "            else:\n",
    "                return res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr = list(accumulate(sorted(x - y for x, y in zip(capacity, rocks))))\n",
    "        # print(arr)\n",
    "        return bisect_right(arr, additionalRocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        return bisect_right([*accumulate(sorted(map(sub, capacity, rocks)))], additionalRocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr = list(accumulate(sorted([(capacity[i] - rocks[i]) for i in range(len(capacity))])))\n",
    "        return bisect_right(arr, additionalRocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        gap = [capacity[i] - rocks[i] for i in range(len(capacity))]\n",
    "        gap.sort()\n",
    "        from itertools import accumulate\n",
    "        gacc = list(accumulate(gap))\n",
    "        flen = len(gap)\n",
    "        for i in range(flen):\n",
    "            if(gacc[i] > additionalRocks):\n",
    "                return i\n",
    "        return flen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:\n",
    "        arr = list(accumulate(sorted(x - y for x, y in zip(capacity, rocks))))\n",
    "        return bisect_right(arr, additionalRocks)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
